/*
提交链接:https://leetcode.cn/problems/number-of-provinces/description/
547. 省份数量
赖德檀 2024/10/7
*/

class Solution {
private:
int* par;
public:
void solu(int n)
{
    par = new int[n];
    for(int i=0;i<n;i++)
    par[i]=i;
}

int find(int x)
{
    if(par[x]!=x)
    par[x]=find(par[x]);
    return par[x];
}

void pair(int a,int b)
{
    par[find(a)]=find(b);
}

    int findCircleNum(vector<vector<int>>& isConnected) {
        int n=isConnected.size();
        int ans=0;
        solu(n);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(isConnected[i][j]==1&&i!=j)
                {
                    pair(i,j);
                }
            }
        }
        set<int>st;
        for(int i=0;i<n;i++)
        st.emplace(find(i));
        return st.size();
    }
};